//438. 找到字符串中所有字母异位词
import java.util.*;
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (p.length() > s.length()) {
            return new ArrayList<>();
        }
        List<Integer> ans = new ArrayList<>();
        int[] hash = new int[26];// p的hash
        int[] hash1 = new int[26];// 窗口
        for (char ch : p.toCharArray()) {
            hash[ch - 'a']++;
        }
        int start = 0;
        int len = 0;
        for (int i = 0; i < s.length(); i++) {
            if (len == p.length()) {
                if (func(hash1, hash)) {
                    ans.add(start);
                }
                hash1[s.charAt(start++) - 'a']--;//去掉窗口的第一个元素
                len--;
            }
            if (hash[s.charAt(i) - 'a'] == 0) {//当前元素不存在于字符串p,直接清空之前的窗口,并且更新start和len
                hash1 = new int[26];
                start = i + 1;
                len = 0;
            } else {
                hash1[s.charAt(i) - 'a']++;//如果存在就++
                len++;
            }
        }
        if (len == p.length()) {//再判断一下，避免最后一个窗口没加上
            if (func(hash1, hash)) {
                ans.add(start);
            }
            hash1[s.charAt(start++) - 'a']--;
            len--;
        }
        return ans;
    }
    //判断当前窗口的元素是否符合
    public static boolean func(int[] hash1, int[] hash) {
        for (int i = 0; i < 26; i++) {
            if (hash[i] != hash1[i]) {
                return false;
            }
        }
        return true;
    }
}